home *** CD-ROM | disk | FTP | other *** search
/ Practical Algorithms for Image Analysis / Practical Algorithms for Image Analysis.iso / TARFILE.GZ / tarfile / ch_4.3 / xah / rfill.c < prev    next >
C/C++ Source or Header  |  1999-09-11  |  4KB  |  204 lines
  1. /* 
  2.  * rfill.c
  3.  * 
  4.  * Practical Algorithms for Image Analysis
  5.  * 
  6.  * Copyright (c) 1997, 1998, 1999 MLMSoftwareGroup, LLC
  7.  */
  8.  
  9. /*
  10.  * R(egion)FILL
  11.  *
  12.  * region growing routines
  13.  */
  14. #include "xah.h"
  15.  
  16. #define    BLACK        0
  17. #define    HALF_WHITE    127
  18. #define    WHITE        255
  19.  
  20.  
  21. #define    WHITE_ON_BLACK    0
  22. #define    BLACK_ON_WHITE    1
  23. #undef DEBUG
  24.  
  25.  
  26.  
  27. /*
  28.  * mark centroid of filled region
  29.  */
  30. void
  31. mark_centroid (double x, double y, int index, int flood_reg_index, Image * aoi)
  32. {
  33.   int ix, iy;
  34.  
  35.   ix = ((x - (int) x) < 0.5 ? (int) x : (int) x + 1);
  36.   iy = ((y - (int) y) < 0.5 ? (int) y : (int) y + 1);
  37.  
  38.   gdImageFill (ix, iy, aoi, flood_reg_index);
  39.   setpixel (ix, iy, aoi, index);
  40. }
  41.  
  42.  
  43.  
  44. /*
  45.  * find leftmost pixel on current line which is interior to region
  46.  */
  47. int
  48. find_left_x (int x, int y, int stop_index, Image * aoi)
  49. {
  50.  
  51.   while (getpixel (x, y, aoi) != stop_index && x > 0)
  52.     x--;
  53.  
  54.   return (++x);
  55. }
  56.  
  57.  
  58. /*
  59.  * fill horiz. line (from left to right)
  60.  */
  61. int
  62. ln_fill (int x, int y, int index, double *xc, double *yc, int stop_index, Image * aoi)
  63. {
  64.   int cindex;
  65.   int ln_ctr;
  66.  
  67.  
  68. /*
  69.  * find leftmost pixel on current line which is interior to region
  70.  */
  71.   x = find_left_x (x, y, stop_index, aoi);
  72.   ln_ctr = 0;
  73.   while ((cindex = getpixel (x, y, aoi)) != stop_index && x < aoi->width) {
  74.     if (cindex != index) {
  75.       //set_pix(x, y, index);
  76.       setpixel (x, y, aoi, index);
  77.       ln_ctr++;
  78.       *xc += (double) x;
  79.       *yc += (double) y;
  80.     }
  81.     x++;
  82.   }
  83.   return (ln_ctr);
  84. }
  85.  
  86.  
  87. /*
  88.  * region raster growing (''fill'') routine, proceeding from seed (x,y):
  89.  * suitable only for convex regions
  90.  */
  91. unsigned int
  92. rfill (int x, int y, int index, double *xc, double *yc, int img_type, Image * aoi)
  93. {
  94.   int ox, oy;
  95.   unsigned int ctr, ln_ctr;
  96.   int cindex, sindex;
  97.   int stop_index;
  98.   int new_ln;
  99.   int up_full, lo_full;
  100.  
  101.   new_ln = 0;
  102.   up_full = lo_full = 0;
  103.   ctr = ln_ctr = 0;
  104.   *xc = *yc = 0.0;
  105.  
  106.   ox = x;
  107.   oy = y;
  108.   sindex = getpixel (x, y, aoi);
  109.   if (img_type == WHITE_ON_BLACK)
  110.     stop_index = BLACK;
  111.   if (img_type == BLACK_ON_WHITE)
  112.     stop_index = WHITE;
  113.  
  114.  
  115. /*
  116.  * fill upper portion of region, line-by-line
  117.  */
  118.   do {
  119.     ln_ctr = ln_fill (x, y, index, xc, yc, stop_index, aoi);
  120.     ctr += ln_ctr;
  121. #ifdef DEBUG
  122.     printf ("   (%d, %d): ln_ctr = %d, ctr = %d\n", x, y, ln_ctr, ctr);
  123. #endif
  124.     if (ln_ctr == 0)
  125.       up_full = 1;
  126.     else {
  127.       x = find_left_x (x, y, stop_index, aoi);
  128.       do {
  129.         if (getpixel (x, y - 1, aoi) == sindex)
  130.           new_ln = 1;
  131.         else
  132.           x++;
  133.       } while (((cindex = getpixel (x, y, aoi)) != stop_index) &&
  134.                (new_ln != 1));
  135.  
  136.       if (new_ln == 0)
  137.         up_full = 1;
  138.       else {
  139.         y--;
  140.         new_ln = 0;
  141.       }
  142.     }
  143.   } while (up_full != 1);
  144.  
  145. /*
  146.  * fill lower portion of region, line-by-line
  147.  */
  148.   new_ln = 0;
  149.   x = ox;
  150.   y = oy;
  151.   x = find_left_x (x, y, stop_index, aoi);
  152.  
  153.   do {
  154.     if (getpixel (x, y + 1, aoi) == sindex)
  155.       new_ln = 1;
  156.     else
  157.       x++;
  158.   } while (((cindex = getpixel (x, y, aoi)) != stop_index) &&
  159.            (new_ln != 1));
  160.  
  161.   if (new_ln == 0)
  162.     lo_full = 1;
  163.   else {
  164.     y++;
  165.     new_ln = 0;
  166.   }
  167.  
  168.  
  169.  
  170.   do {
  171.     ln_ctr = ln_fill (x, y, index, xc, yc, stop_index, aoi);
  172.     ctr += ln_ctr;
  173. #ifdef DEBUG
  174.     printf ("   (%d, %d): ln_ctr = %d, ctr = %d\n", x, y, ln_ctr, ctr);
  175. #endif
  176.     if (ln_ctr == 0)
  177.       lo_full = 1;
  178.     else {
  179.       x = find_left_x (x - 1, y, stop_index, aoi);
  180.       do {
  181.         if (getpixel (x, y + 1, aoi) == sindex)
  182.           new_ln = 1;
  183.         else
  184.           x++;
  185.       } while (((cindex = getpixel (x, y, aoi)) != stop_index) &&
  186.                (new_ln != 1));
  187.  
  188.       if (new_ln == 0)
  189.         lo_full = 1;
  190.       else {
  191.         y++;
  192.         if (y >= aoi->height) {
  193.           printf ("Something wrong.  y value too big %d.\n", y);
  194.           ImageOut ("imgdump.tif", aoi);
  195.           exit (1);
  196.         }
  197.         new_ln = 0;
  198.       }
  199.     }
  200.   } while (lo_full != 1);
  201.  
  202.   return (ctr);
  203. }
  204.